package com.zhangll.core.operatingsystem;

import scala.Int;

import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;

/**
 *  MMU memory manage unit 内存管理单元
 *  其内部有一张页表，专用的地址翻译过程也是由其计算，比如乘法高效执行（位移）
 *  分页的管理，定义页表，tlb？
 */
public class MMUDemo {
    public static void main(String[] args) {
        int page_number = 20000;
//        String format = String.format("%", page_number);
        String s = Integer.toBinaryString(page_number);
        System.out.println(s);

        // 页长: 一个页有一定的长度，所有页的综合为页表。页表记录了页号和偏移量，每个页的长度
        int page_len = 2 * 1024;

        // 偏移量
        int bais = 10;

        // 物理地址
        int metirialpath = page_number * page_len + bais;
        System.out.println(metirialpath);
        // 问题，多进程比如1000个进程，如果共用内存空间，那么如何管理这些进程呢？
        // 如何保证在在有限内存空间的操作系统中能够支持上万等等的进程呢？
        // 基于一个统计事实，在进程执行阶段，只有一小部分的代码是被执行的。其他代码
        // 驻留在内存空间中会引起浪费。可以把这些不怎么用到的代码数据保存在磁盘中。
        // 按需加载到内存中，一旦有需要用到代码段。

        // 在这些被存储到磁盘中的某些代码片段可能是被多个进程共同享用的，因此抽象
        // 出一个shared page，让多个进程共享这个页，并通过MMU访问到共享的物流空间中的
        // 代码段，从而实现复用。复用也是计算机设计与代码实现上要考虑的重大问题。

        // 进程是一组指令集合，为了满足一个大目标
        //   /\           ||
        //   | run        ||
        //   |            \/
        //   |          页表，快速访问物理地址-----------> 操作系统介入换入换出页表项
        // 物理地址 《----|

        // 因此 按需调页 demand paging，会被应用，当然demand segment也是可以的

        // 动态内存虚拟管理！！！体系
        //示意 三种情况的产生
        // 1. 在cpu逻辑地址访问内存物流地址的时候，通过MMU 访问TLB页表（或者直接访问内存中的页表信息），并找到相应的页帧。
        // 2. 非法访问，不存在页帧且超过了实际物理内存和磁盘中的
        // 3. 合法访问，当不存在物理页帧（设计 a valid-invalid bit 一个有效位 v 页面驻留内存，i 页面不存在或非法访问），但是有页帧，且由于虚拟管理的出现，而使得页帧在磁盘空间中是存在的
        // 页面的换入换出（并不是代码的，那代码什么时候加载进去的呢）。
        // -------------------------------------demond paging 算法----------------------------------------------
        // one page   init                                    running
        // */ --------------------- *              */ --------------------- *
        //  | i                     |              | v                     |
        //  |                       |              |                       |
        //  |         物理          |              |                       |
        //  |   (exists or not)     |              |                       |
        //  * --------------------- */              * --------------------- */
        //             ||
        //             ||
        //             ||                                     same   <<<<----------------------
        //             ||                                                                     |
        //             \/                                                                     |
        //        修改中断响应                                                                |
        //      非法        合法   （MMU不用管，仍然是call 0）                                |
        //                   含有物理空间，但是此时的页表项中的avib是i状态                    |  (由页帧但是失效，目的是要把页帧对应的页以及代码加载到内存中)
        //                                          load                                      |  (硬件控制加载)
        //                            此时就由操作系统去加载页面到物理空间中                  |  (页面是存硬盘的，不一定是页面，看操作系统怎么设计，是否要加载代码片段呢？)
        //                  并把当前page的avib置为v        其他进程的页表项的avib状态置为i    |
        //                         属性tlb，再重走一次    ------------------------------------   (PC寄存器的调整)

        // 优势，70 80无用代码不用载入，io less，内存减少了 m less， faster响应， more users
        // lazy swapper，需要的时候才唤醒换入换出。是一个睡眠进程

        // ***每个进程都有一个假设一个页长度位4k***，那么需要4M大小的空间来存储4G的映射（4G/ 4K）



        // 页表项内容i386（an item of page）
        //  /*----------------------------------------------*
        //   |  31 ----------12----6-5------2-----1----0    |
        //   |  页帧物理地址  |    D|A  |  U/S | R/W | P    |
        //   *----------------------------------------------*/
        // D 已写标志 dirty  内存中的与硬盘中的页面不一致，即有改写内容了？改写了哪些内容？
        // A 访问位 一旦访问就access =1 ，初始化为0  reference bit
        // U/S = 1 可以在任何权限下访问。内核态和用户态都可以
        // U/S = 0 特权级0 1 2下访问
        // R/W = 1 写/读/执行
        // R/W = 0 读/执行    不可写
        // P = 1 地址转换有效，无效，对应上面的 avib标志

        // 缺页导致的换入换出操作是一个比较耗时的操作。当缺页率为1%%（每1000次调用出现一次缺页）
        // 比非缺页的情况会慢了40倍，这个也是多道程序需要面临的一个问题，要去解决这个问题
        // 置换算法的高效性能是非常有必要研究的

        // 缺页响应      流程   -----------> 缺页率，最求最低。=====》评估方法为 内存引用 reference string，累积缺页次数 ====
        //  /*---------------------------------------------*                                                                ||
        //   |  1. 确定逻辑页面在交换区的位置              |                                                                ||
        //   |  2. 确定内存空间中的空闲页帧（free frame）  |（如果内存空间不足，就evict一个占用的页帧）                     ||
        //   |  3. 换入交换区中的逻辑页面                  |                   |                                            ||
        //   |  4. 返回中断进程，reexec                    |                   |                                            只要涉及到页号就行了
        //   *---------------------------------------------*/                  |                                            页内偏移量的访问也是由页号确定
        //                                                                     |                                            简化计算（1）
        //                                                                     |                                            ||
        //   页面置换算法<----------------------------------------------------- 换出的时候可以参考dirty是否为0              ||
        //       ||                                                             0 表示交换区已经有一份最新的copy            ||
        //       ||                                                             不做换出操作，直接删除（2）                 ||
        //       ||                                                                                                         ||
        //      1. FIFO                              <======================================================================||
        //       ||----》 1,2,3,4,1,2,5,1,2,3,4,5 （页号）     3个物理页帧，每次换入换成都要累积   reference string         ||
        //       ||           缺页9次(3个页帧)                                                                              ||
        //       ||           1   4   5                                                                                     ||
        //       ||           2   1   3                                                                                     ||
        //       ||           3   2   4                                                                                     ||
        //       ||                                                                                                         ||
        //       ||           缺页10次(4个页帧)                                                                             ||
        //       ||           1   5   4                                                                                     ||
        //       ||           2   1   5                        (????物理页帧变大，缺页次数增加？？？？)                     ||
        //       ||           3   2                                                                                         ||
        //       ||           4   3                                                                                         ||
        //      2. Optimize（理想的，不能预测后一页）<======================================================================||
        //       ||----》 1,2,3,4,1,2,5,1,2,3,4,5 （页号）     3个物理页帧，每次换入换成都要累积   reference string         ||
        //       ||           缺页6次  (4个页帧)                                                                            ||
        //       ||           1                                                                                             ||
        //       ||           2   4                                                                                         ||
        //       ||           3                                                                                             ||
        //       ||           4   5                                                                                         ||
        //       ||                                                                                                         ||
        //     3. LRU 效果好，无法用数学推导（最长时间不用）                                                                ||
        //       ||----》 1,2,3,4,1,2,5,1,2,3,4,5 （页号）     3个物理页帧，每次换入换成都要累积   reference string         ||
        //       ||           缺页8次  (4个页帧)                                                                            ||
        //       ||           1       5                                                                                     ||
        //       ||           2                                                                                             ||
        //       ||           3   5   4                                                                                     ||
        //       ||           4   3                                                                                         ||
        lru(); //|| 目前所有的操作系统都用lru来处理页面置换的问题
        //       ||                                                                                                         ||
        //     4. 近似LRU算法                                                                                               ||
        //       ||                                                                                                         ||
        //     思想为用reference bit    =》 5 号位，总是换出引用位为0的，没有被使用的
        //     second chance  添加一个引用，引用位为1的化，先置为0，后期再使用（避免全部为1 的情况死循环）
        //     5.  counting 算法
        //      LFU (计数值最小)MFU（计数值最大） 最小好还是最大好，还是需要实践的


        // 两个小问题
        // 1. 进程刚创建的时候是否需要页面（放入内存中）
        //   mov指令 6个字节   ，可能横跨2个页面    ========| mov |========   指令上部分一个页面
        //                                                 |  adr  |    ========> 源数据块，一个页面
        //                                          ========| adr |========   指令下部分一个页面
        //                                                     | ========>  目标数据块，一个页面
        //  共需要4个页面，所以确定最小页面还是很有必要的。如果只有一个页面，那就根本无法执行
        // linux最小的页面数位1，就是内核中的堆栈页面，这个只要一个页面，把堆栈的头地址给到pcb（进程文件），共享堆栈
        // 两种分配页帧的算法
        // fixed allocation，策略
        // 1.  平均算法（a）
        // 2.  按照进程的镜像占用的逻辑空间比分配页帧（b）
        // Priority allocation
        // 优先级 pr = 1  分配的时候按比例，当P1产生缺页，那么换出pr比较低的进程

        // 2.抖动，thrashing
        // 缺页而频繁地换入换出操作，io提高，而减少了cpu使用效率
        // 如果为了并行而增加进程，那么会有恶性循环   两个页帧用于一条movsb命令，此时时会不断恶性循环（局部性的交换页帧）
        // 可以使用window计算，计算工作集中的内容，然后全局计算工作集中的
    }

    private static void lru(){


        // 在操作系统中，获取多长时间没有引用
        // 每个页表项 都有一个计数器
        // 计数的是当前倍更新时候的  时钟值
        // 调用置换算法时，选取计数器最早的页面，换出，可以用小堆数据结构来存储（操作系统是遍扫描）

        // 第二种算法是使用堆栈，双向链表，linkedHashMap
        // 使用的是先前的数据，因此会有比较好的性能
        int[] pageNum = new int[]{7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
        int count = 0;
        // 3物理帧
        int pageFrameSize = 3;
        LinkedHashMap<Integer,Integer> map = new LinkedHashMap<Integer,Integer>(pageFrameSize,0.7f,true);
        LinkedHashSet<Integer> set = new LinkedHashSet<Integer>(pageFrameSize,0.7f);

        for (int i = 0; i < pageNum.length; i++) {
            Integer integer = map.get(pageNum[i]);
            if(integer == null){
                count += 1;
                if( map.size() >= pageFrameSize) {
                    Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
                    Integer key = entries.iterator().next().getKey();
                    System.out.print("remove:" + key + " and ");
                    map.remove(key);
                }
                map.put(pageNum[i],1);
                System.out.println("insert:" + pageNum[i]);
                System.out.println("reuslt: " + map.keySet());
            } else {
                System.out.println("jump: "+ pageNum[i]);
            }
        }
        System.out.println("count:" + count);


    }

}
